home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / mawk10.zip / ARRAY.C < prev    next >
C/C++ Source or Header  |  1991-10-05  |  9KB  |  361 lines
  1.  
  2. /********************************************
  3. array.c
  4. copyright 1991, Michael D. Brennan
  5.  
  6. This is a source file for mawk, an implementation of
  7. the AWK programming language.
  8.  
  9. Mawk is distributed without warranty under the terms of
  10. the GNU General Public License, version 2, 1991.
  11. ********************************************/
  12.  
  13. /* $Log:    array.c,v $
  14.  * Revision 3.3.1.1  91/09/14  17:22:35  brennan
  15.  * VERSION 1.0
  16.  * 
  17.  * Revision 3.3  91/08/13  06:50:44  brennan
  18.  * VERSION .9994
  19.  * 
  20.  * Revision 3.2  91/06/28  04:16:00  brennan
  21.  * VERSION 0.999
  22.  * 
  23.  * Revision 3.1  91/06/07  10:26:48  brennan
  24.  * VERSION 0.995
  25.  * 
  26.  * Revision 2.3  91/05/22  07:39:40  brennan
  27.  * static prototypes
  28.  * 
  29.  * Revision 2.2  91/05/15  12:07:27  brennan
  30.  * dval hash table for arrays
  31.  * 
  32.  * Revision 2.1  91/04/08  08:22:15  brennan
  33.  * VERSION 0.97
  34.  * 
  35. */
  36.  
  37. #include "mawk.h"
  38. #include "symtype.h"
  39. #include "memory.h"
  40. #include "bi_vars.h"
  41.  
  42. /* convert doubles to string for array indexing */
  43. #define   A_FMT         "%.6g"
  44.  
  45. static ANODE *PROTO(find_by_sval, (ARRAY, STRING *, int) ) ;
  46. static D_ANODE *PROTO(find_by_dval, (ARRAY, double , int) ) ;
  47.  
  48. extern int returning ; 
  49.    /* flag -- on if returning from function call */
  50.  
  51. extern unsigned hash() ;
  52.  
  53. /* An array A is a pointer to an array of struct array,
  54.    which is two hash tables in one.  One for strings
  55.    and one for doubles.
  56.  
  57.    each array is of size A_HASH_PRIME.
  58.  
  59.    When an index is deleted via  delete A[i], the
  60.    ANODE is not removed from the hash chain.  A[i].cp
  61.    and A[i].sval are both freed and sval is set NULL.
  62.    This method of deletion simplifies for( i in A ) loops.
  63.  
  64.    On the D_ANODE list, we use real deletion and move to the
  65.    front on access.
  66.  
  67.    Separate nodes (as opposed to one type of node on two lists)
  68.    to
  69.      (1) d1 != d2, but sprintf(A_FMT,d1) == sprintf(A_FMT,d1)
  70.          so two dnodes can point at the same anode.
  71.      (2) Save a little data space(64K PC mentality).
  72.  
  73.    the cost is an extra level of indirection.
  74.  
  75.    Some care is needed so that things like
  76.      A[1] = 2 ; delete A["1"] work .
  77. */
  78.  
  79. #define  _dhash(d)    (((int)(d)&0x7fff)%A_HASH_PRIME)
  80. #define  DHASH(d)     (last_dhash=_dhash(d))
  81. static  unsigned  last_dhash ;
  82.  
  83.  
  84. static  ANODE *find_by_sval(A, sval, cflag)
  85.   ARRAY  A ;
  86.   STRING *sval ;
  87.   int  cflag ; /* create if on */
  88. { 
  89.    char *s = sval->str ;
  90.    unsigned h = hash(s) % A_HASH_PRIME ;
  91.    register ANODE *p = A[h].link ;
  92.    ANODE *q = 0 ; /* holds first deleted ANODE */
  93.  
  94.    while ( p )
  95.    {
  96.      if ( p->sval )
  97.      { if ( strcmp(s,p->sval->str) == 0 )  return p ; }
  98.      else /* its deleted, mark with q */
  99.      if ( ! q )  q = p ;  
  100.  
  101.      p = p->link ;
  102.    }
  103.  
  104.    /* not there */
  105.    if ( cflag )
  106.    {
  107.        if ( q )  p = q ; /* reuse the deleted node q */
  108.        else
  109.        { p = (ANODE *)zmalloc(sizeof(ANODE)) ;
  110.          p->link = A[h].link ; A[h].link = p ;
  111.        }
  112.  
  113.        p->sval = sval ;
  114.        sval->ref_cnt++ ;
  115.        p->cp = (CELL *) zmalloc(sizeof(CELL)) ;
  116.        p->cp->type = C_NOINIT ;
  117.    }
  118.    return p ;
  119. }
  120.  
  121.  
  122. /* on the D_ANODE list, when we find a node we move it
  123.    to the front of the hash chain */
  124.  
  125. static D_ANODE  *find_by_dval(A, d, cflag)
  126.   ARRAY  A ;
  127.   double d ;
  128.   int cflag ;
  129. {
  130.   unsigned h = DHASH(d) ;
  131.   register D_ANODE *p = A[h].dlink ;
  132.   D_ANODE *q = 0 ; /* trails p for move to front */
  133.   ANODE *ap ;
  134.  
  135.    while ( p )
  136.        if ( p->dval == d )
  137.        { /* found */
  138.          if ( ! p->ap->sval ) /* but it was deleted by string */
  139.          { if ( q )  q->dlink = p->dlink ;
  140.            else A[h].dlink = p->dlink ;
  141.            zfree(p, sizeof(D_ANODE)) ;
  142.            break ; 
  143.          }
  144.          /* found */
  145.          if ( !q )  return  p ; /* already at front */
  146.          else /* delete to put at front */
  147.          { q->dlink = p->dlink ; goto found ; }
  148.        }
  149.        else
  150.        { q = p ; p = p->dlink ; }
  151.  
  152.    /* not there, still need to look by sval 
  153.       CANNOT use temp_buff, may be in use by split */
  154.    
  155.    { char xbuff[16] ;
  156.      STRING *sval ;
  157.  
  158.      (void) sprintf(xbuff, A_FMT, d) ;
  159.      sval = new_STRING(xbuff) ;
  160.      ap = find_by_sval(A, sval, cflag) ;
  161.      free_STRING(sval) ;
  162.    }    
  163.  
  164.    if ( ! ap )  return (D_ANODE *) 0 ;
  165.    /* create new D_ANODE  */
  166.    p = (D_ANODE *) zmalloc(sizeof(D_ANODE)) ;
  167.    p->ap = ap ; p->dval = d ;
  168.  
  169. found : /* put p at front */
  170.    p->dlink = A[h].dlink ; A[h].dlink = p ;
  171.    return p ;
  172. }
  173.  
  174. CELL *array_find(A, cp, create_flag)
  175.   ARRAY A ;
  176.   CELL *cp ;
  177.   int create_flag ;
  178. {
  179.   ANODE *ap ;
  180.   D_ANODE *dp ;
  181.  
  182.   switch( cp->type )
  183.   {
  184.     case C_DOUBLE :
  185.         return  (dp = find_by_dval(A, cp->dval, create_flag))
  186.                 ? dp->ap->cp : (CELL *) 0 ;
  187.  
  188.     case  C_NOINIT :
  189.         ap = find_by_sval(A, &null_str, create_flag) ;
  190.         break ;
  191.  
  192.     default :
  193.         ap = find_by_sval(A, string(cp), create_flag) ;
  194.         break ;
  195.   }
  196.  
  197.   return  ap ? ap->cp : (CELL *) 0 ;
  198. }
  199.  
  200.  
  201. void  array_delete(A, cp)
  202.   ARRAY A ; CELL *cp ;
  203. {
  204.   ANODE *ap ;
  205.   D_ANODE *dp ;
  206.  
  207.   switch( cp->type )
  208.   {
  209.     case C_DOUBLE :
  210.         if ( !(dp = find_by_dval(A, cp->dval, 0)) ) return ;
  211.  
  212.         ap = dp->ap ;
  213.         /* dp is at front of A[last_dhash], delete the D_ANODE */
  214.         A[last_dhash].dlink = dp->dlink ;
  215.         zfree(dp, sizeof(D_ANODE)) ;
  216.         break ;
  217.  
  218.     case  C_NOINIT :
  219.         ap = find_by_sval(A, &null_str, 0) ;
  220.         break ;
  221.  
  222.     default :
  223.         ap = find_by_sval(A, string(cp), 0) ;
  224.         break ;
  225.   }
  226.  
  227.   if ( ap )
  228.   { free_STRING(ap->sval) ; ap->sval = (STRING *) 0 ;
  229.     cell_destroy(ap->cp)  ; zfree(ap->cp, sizeof(CELL)) ;
  230.   }
  231. }
  232.  
  233.  
  234.  
  235. /* for ( i in A ) ,
  236.    loop over elements of an array 
  237.  
  238. sp[0].ptr :  a pointer to A ( the hash table of A)
  239. sp[-1] :  a pointer to i ( a cell ptr)
  240.  
  241. cdp[0] :  a stop op to catch breaks
  242. cdp[1] :  offset from cdp of the code after the loop (n+2)
  243. cdp[2] :  start of body of the loop
  244. cdp[3..n] : the rest of the body
  245. cdp[n+1]  : a stop op to delimit the body and catch continues
  246. */
  247.  
  248. INST  *array_loop( cdp, sp, fp) /* passed code, stack and frame ptrs */
  249.   INST *cdp ; 
  250.   CELL *sp, *fp ;
  251. { int i ;
  252.   register ANODE *p ;
  253.   ARRAY   A = (ARRAY) sp-- -> ptr ;
  254.   register CELL *cp = (CELL *) sp-- -> ptr ;
  255.  
  256.   for ( i = 0 ; i < A_HASH_PRIME ; i++ )
  257.   for ( p = A[i].link ; p ; p = p->link )
  258.   { if ( ! p->sval /* its deleted */ )  continue ;
  259.   
  260.     cell_destroy(cp) ;
  261.     cp->type = C_STRING ;
  262.     cp->ptr = (PTR) p->sval ;
  263.     p->sval->ref_cnt++ ;
  264.  
  265.     /* execute the body of the loop */
  266.     if ( execute(cdp+2, sp, fp) == cdp /* exec'ed a break statement */
  267.          || returning  /* function return in body of loop */
  268.        )  
  269.            goto break2 /* break both for loops */ ; 
  270.   }
  271.  
  272. break2 :
  273.   return   cdp + cdp[1].op ;
  274. }
  275.  
  276.  
  277. /* cat together cnt elements on the eval stack to form
  278.    an array index using SUBSEP */
  279.  
  280. CELL *array_cat( sp, cnt)
  281.   register CELL *sp ;
  282.   int cnt ;
  283. { register CELL *p ;  /* walks the stack */
  284.   CELL subsep ;  /* a copy of bi_vars[SUBSEP] */
  285.   unsigned subsep_len ;
  286.   char *subsep_str ;
  287.   unsigned total_len ; /* length of cat'ed expression */
  288.   CELL *top ;  /* sp at entry */
  289.   char *t ; /* target ptr when catting */
  290.   STRING *sval ;  /* build new STRING here */
  291.  
  292.   /* get a copy of subsep, we may need to cast */
  293.   (void) cellcpy(&subsep, bi_vars + SUBSEP) ;
  294.   if ( subsep.type < C_STRING ) cast1_to_s(&subsep) ;
  295.   subsep_len = string(&subsep)->len ;
  296.   subsep_str = string(&subsep)->str ;
  297.   total_len = --cnt * subsep_len ;
  298.  
  299.   top = sp ;
  300.   sp -= cnt ;
  301.   for( p = sp ; p <= top ; p++ )
  302.   {
  303.     if ( p->type < C_STRING ) cast1_to_s(p) ;
  304.     total_len += string(p)->len ;
  305.   }
  306.  
  307.   sval = new_STRING((char *)0, total_len) ;
  308.   t = sval->str ;
  309.  
  310.   /* put the pieces together */
  311.   for( p = sp ; p < top ; p++ )
  312.   { (void) memcpy(t, string(p)->str, SIZE_T(string(p)->len)) ;
  313.     (void) memcpy( t += string(p)->len, subsep_str, SIZE_T(subsep_len)) ;
  314.     t += subsep_len ;
  315.   }
  316.   /* p == top */
  317.   (void) memcpy(t, string(p)->str, SIZE_T(string(p)->len)) ;
  318.  
  319.   /* done, now cleanup */
  320.   free_STRING(string(&subsep)) ;
  321.   while ( p >= sp )  { free_STRING(string(p)) ; p-- ; }
  322.   sp->type = C_STRING ;
  323.   sp->ptr = (PTR) sval ;
  324.   return sp ;
  325. }
  326.  
  327.  
  328. /* free all memory used by an array,
  329.    only used for arrays local to a function call
  330. */
  331.  
  332. void  array_free(A)
  333.   ARRAY  A ;
  334. { register ANODE *ap ;
  335.   register D_ANODE *dp ;
  336.   register int i ;
  337.   ANODE *aq ;
  338.   D_ANODE *dq ;
  339.  
  340.   for( i = 0 ; i < A_HASH_PRIME ; i++ )
  341.   { ap = A[i].link ;
  342.     while ( ap )
  343.     { /* check its not a deleted node */
  344.       if ( ap->sval )
  345.       { free_STRING(ap->sval) ;
  346.         cell_destroy(ap->cp) ;
  347.         free_CELL(ap->cp) ;
  348.       }
  349.  
  350.       aq = ap ; ap = ap->link ;
  351.       zfree( aq, sizeof(ANODE)) ;
  352.     }
  353.  
  354.     dp = A[i].dlink ;
  355.     while ( dp )
  356.     { dq = dp ; dp = dp->dlink ; zfree(dq,sizeof(D_ANODE)) ; }
  357.   }
  358.  
  359.   zfree(A, sizeof(A[0]) * A_HASH_PRIME ) ;
  360. }
  361.